package com.gwcloud.leetcode.hot100;

/** 
* @ClassName   : Leetcode121 
* @author      : ganwei 
* @date        : 2020年4月29日 
* @Description : leetcode 121. 买卖股票的最佳时机 
*/
public class Leetcode0121 {

	/** 
	 * 解题思路-滑窗算法
	 * 优化版暴力解法，该方法比较妖
	 */
    public static int maxProfit(int[] prices) {
    	int len = prices.length;
    	//如果数组小于2，直接返回
    	if(len < 2) {
    		return 0;
    	}
    	
    	int res = 0;
    	
    	// 表示在当前位置之前的最小值，假设修正法（打擂台法）
    	int minval = prices[0];
    	// 注意：这里从 1 开始
    	for(int p : prices) {
    		res = Math.max(res, p - minval);
    		minval = Math.min(minval, p);
    	}
    	
    	return res;
    	
    }
    /**
     * 解题思路-动态规划
     */
    public static int maxProfit_1(int[] prices) {
		int len = prices.length;
		if (len < 2) {
			return 0;
		}

		int[][] dp = new int[len][3];
		// 0：不进行任何操作
		// 1：用户执行了一次买入
		// 2：用户执行了一次卖出
		dp[0][0] = 0;
		dp[0][1] = -prices[0];
		dp[0][2] = 0;
		for (int i = 1; i < len; i++) {
			dp[i][0] = 0;
			dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
			dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
		}
		return Math.max(dp[len - 1][2], dp[len - 1][0]);

    }
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] pp = {7,1,5,3,6,4};
		System.out.println(maxProfit_1(pp));
	}

}
